package tasks.leetcode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 使用双向队列，解决 leetcode 239 滑动窗口问题
 */
public class SlidingMaxValue {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        // 创建一个双向队列
        Deque<Integer> deque = new ArrayDeque<>();
        int[] result = new int[nums.length - k + 1];

        for (int i = 0; i < nums.length; i++) {
            // deque.peekFirst() 只是取出第一个元素来看，不会从该队列移除该元素
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                // 移除第一个元素
                deque.pollFirst();
            }
            //  // deque.peekLast() 只是取出最后一个来看，不会从该队列移除该元素
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                // 移除最后一个元素
                deque.pollLast();
            }
            // 将当前元素加入队列,i是当前数组的索引
            deque.offer(i);

            if (i>=k-1) {
                result[i-k+1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] maxSlidingWindow = new SlidingMaxValue().maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
        for (int i : maxSlidingWindow) {
            System.out.print(i + ",");
        }
    }
}